#include <stdio.h>
#include <string.h>

/*
    KMP 需要一个相比较暴力解法来说的区别在于next 数组的建立，
    所以第一件事情就是要搞清楚next 数组是怎么来的额
    next数组是 在统计出随着窗口滑动之后每一步的公共前后缀的长度
    便于我们在求解的过程中能够更好的进行跳跃
    1. 什么是前缀 
    请公主作答 ： 

    2. 什么是后缀 
    请公主作答 ： 


*/
/*
    好了 在知道公共前后缀怎么找了之后 我们就可以来创建next数组了
    第一件事 因为第一个位置的 元素不论是什么元素 前后都没有 所以next[0] 一定是 0
    然后两个指针 一个计数和作为慢指针 一个快的用于比较  之后经典分情况讨论 ：
    一般情况 ： 如果存在公共部分 计数++   同时 把 计数的结果给到当前的循环next
    特殊情况 ： 如果存在说计数大于0  但是不相同，那就回溯到上一次的结果 
    （月光宝盒 ： 菠萝菠萝蜜！）
*/
void buildNext(char* pattern, int* next,int subLen);



// 我们拿到next数组之后呢，我们就可以来实现这个算法


/*
    KMP_set 首先判断是否是合法的，那不合法的确实有两种情况 
     1. 子串空  或者  子串比 主串还要长 (子串 和  主串 是什么 模式串又是什么) 
     2. 子串为空  或者  子串长度是 0 
    然后把所有字符串长度拿过来 申请一块内存来保存next 数组 
    然后 buildNext把你的参数传进去 
    还是双指针一个子串一个主串 遍历主串 特殊情况主串和子串不相等 
    一般情况下 相同 就 计数++  如果找到了子串 那就返回主去掉子串的长度 (加不加一取决于位置还是索引)
    出循环就 释放内存 返回表示没找到 
*/
int KMP_set(char* text,char* pattern);


/*
    至于说如果是暴力解的话 
    首先确定两个串是合法的 然后拿到两个串的长度
    然后双指针 一个主串一个子串分别比长度小表示没有到头 
    相等就移动 
    不等子串和主串回到每一个的初始状态  - 子串是 0  主串是去掉子串的部分
    如果子串找到 返回子串初始位置 
    找不到返回-1
*/
int pure_force(char* text,char* pattern);



int main(){
    return 0;
}